//
//  18. 四数之和.swift
//  LeetCodeTrain
//
//  Created by rjb on 2021/7/14.
//  Copyright © 2021 rjb. All rights reserved.
//

import Foundation

class Solution18 {
    // 与三数之和类似
    func fourSum(_ nums: [Int], _ target: Int) -> [[Int]] {
        var result: [[Int]] = []
        guard nums.count >= 4 else {
            return []
        }
        // o(nlong), 为了保证不重复，相连接的不能相同
        let sortedNums = nums.sorted()
        for i in 0..<sortedNums.count {
            // 去重
            if i > 0 && sortedNums[i] == sortedNums[i - 1] {
                continue
            }
            for j in i + 1..<sortedNums.count {
                // 去重
                if j > i + 1 && sortedNums[j] == sortedNums[j - 1] {
                    continue
                }
                var left = j + 1
                var right = sortedNums.count - 1
                // 采用双指针法，能将降低一层循环
                while left < right {
                    let sum = sortedNums[left] + sortedNums[right] + sortedNums[i] + sortedNums[j]
                    if sum == target {
                        result.append([sortedNums[i], sortedNums[j], sortedNums[left], sortedNums[right]])
                        // 当相等时,p1 与 p2 去重
                        while left < right, sortedNums[left] == sortedNums[left + 1] {
                            left += 1
                        }
                        while left < right, sortedNums[right] == sortedNums[right - 1] {
                            right -= 1
                        }
                        right -= 1
                        left += 1
                    } else if sum > target {
                        right -= 1
                    } else {
                        left += 1
                    }
                }
            }
        }
        return result
    }
    static func test() {
        let solution = Solution18()
        let nums = [-1,0,1,2,-1,-4]
        let target =  -1
        let result = solution.fourSum(nums, target)
        print(result)
    }
}
